package solution;

/**
 * <a href="https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&&tqId=11154&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking">
 * JZ1 二维数组中的查找</a>
 *
 * @author or2
 * @Description 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * @create 2021年09月08日 时间: 11:09
 */
public class Find {
    public boolean find(int target, int[][] array) {
        int lineLength = array.length;
        int rowLength = array[0].length;

//        特殊边界处理
        if (array[0].length == 0 || array[0][0] > target) {
            return false;
        }
//        处理最右边界条件
        for (int[] ints : array) {
            int cur = ints[rowLength - 1];
            if (cur == target) {
                return true;
            } else if (cur > target) {
                break;
            }
        }
//        最下方边界
        for (int i = 0; i < rowLength; i++) {
            int cur = array[lineLength - 1][i];
            if (cur == target) {
                return true;
            } else if (cur > target) {
                break;
            }
        }

//        正式处理
        int line = 0, row = 0;
//        右边界自动换行, 仅考虑左边界便可
        while (line < lineLength - 1) {
            int compare = Integer.compare(array[line][row], target);
            switch (compare) {
                case 0:
                    return true;
                case -1:
                    row++;
//                    换行操作 - ① 到右边界时换行, ② 当前行找不到目标值
                    if (array[line][row] > target || row == rowLength - 1) {
                        row--;
                        line++;
                    }
                    break;
                case 1:
                    row--;
                    if (row < 0) {
                        return false;
                    }
                    break;
            }
        }

        return false;
    }
}
